package code.class4;

/**
 * https://leetcode.cn/problems/gas-station/description/
 * 加油站的良好出发点
 */
public class Code04_GasStation {

    public static void main(String[] args) {
        int[] gas = {1, 6, 3, 4, 10}; // 油量
        int[] cost = {3, 4, 5, 2, 2}; // 距离
        //          -2  2 -2  2  8
        int startIndex = canCompleteCircuit2(gas, cost);
        System.out.println("startIndex = " + startIndex);
    }

    public static int canCompleteCircuit2(int[] gas, int[] cost) {
        int minBalance = 0, n = gas.length, minIndex = 0, balance = 0;

        for (int i = 0; i < n; i++) {
            balance += gas[i] - cost[i];
            if (balance < minBalance) {
                minBalance = balance;
                minIndex = (i + 1) % n;
            }
        }
        return balance >= 0 ? minIndex : -1;
    }

    public static int canCompleteCircuit(int[] gas, int[] cost) {
        int sum, l = 0, r = 0, n = gas.length, k;
        for (; l < n; l = r + 1, r = l) {
            sum = 0;
            k = gas[r % n] - cost[r % n];
            while (sum + k >= 0) {
                if (r - l + 1 == n) {
                    return l;
                }
                sum += k;
                r++;
            }
        }
        return -1;
    }
}
